package com.sicheng.algorithm.recursive.dfs;

import org.junit.Test;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/1/9 21:52
 */
public class 符号三角形 {
    int half,//符号三角形中符号数目的一半
            n,//第一行符号个数
            count;//当前"+"的个数
    int[][] p;//符号三角存放
    long result;//符号三角形的符号个数(防止符号过多,声明为long类型)


    @Test
    public void test() {
        compute(4);
        System.out.println(result);
    }

    public void compute(int n) {
        half = (n * (n + 1)) >> 1;//先让half=符号的总数
        if (half >> 1 << 1 != half)
            return;

        p = new int[n + 1][n + 1];
        half = half >> 1;
        this.n = n;
        dfs(1);

    }

    private void dfs(int t) {
        //判断上一轮是否符合
        if (count > half || (t * (t - 1) >> 1) - count > half) {
            //+ 或 -大于总数一半剪枝
            return;
        }

        if (t > n) {
            result++;
            return;
        }

        for (int i = 0; i <= 1; i++) {
            p[1][t] = i;
            count += i;
            //操作
            for (int j = 2; j <= t; j++) {
                //这里可能有一些难推导，第t列的这个符号只能影响下面几行t列之前的符号
                //如果当前行为k,下面的行数为j，则t最多可以影响到的列数为t-(j-k)即为t-j+k
                //在一行中即为t-j+1
                p[j][t - j + 1] = p[j - 1][t - j + 1] ^ p[j - 1][t - j + 2];
                count += p[j][t - j + 1];
                //只能为0或者1
            }
            dfs(t + 1);
            //回溯撤销操作

            for (int j = 2; j <= t; j++) {
                count -= p[j][t - j + 1];//只能为0或者1
            }
            count -= i;
        }

    }
}
